package com.example.Arithmetic.Lettcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 日期：2024/1/3
 * 时间：11:44
 * 描述：N皇后问题，同行同列，左右斜线不可以放，求8*8棋盘可以放解法
 */
public class E01Lettcode51 {
    public static List<List<String>> solveNQueens(int n) {
        boolean[] ca = new boolean[n];          //列冲突
        boolean[] cb = new boolean[n * 2 - 1];  //左斜线冲突
        boolean[] cc = new boolean[n * 2 - 1];  //右斜线冲突
        char[][] table = new char[n][n];
        for (char[] c : table) {
            Arrays.fill(c, '.');
        }
        List<List<String>> list = new ArrayList<>();
        dfs(0, n, table, ca, cb, cc, list);
        return list;
    }

    private static void dfs(int i, int n, char[][] table, boolean[] ca, boolean[] cb, boolean[] cc, List<List<String>> list) {
        if (i == n) {      //找到解
            ArrayList arrayList = new ArrayList();
            for (char[] chars : table) {
                arrayList.add(String.valueOf(chars));
            }
            list.add(new ArrayList<>(arrayList));
        }
        for (int j = 0; j < n; j++) {
//            减枝，判断冲突状态
            if (ca[j] || cb[i + j] || cc[n - 1 + (i - j)]) {
                continue;
            }
//            记录冲突和皇后位置
            table[i][j] = 'Q';
            ca[j] = cb[i + j] = cc[n - 1 + (i - j)] = true;
//            递归下一行
            dfs(i + 1, n, table, ca, cb, cc, list);
//            恢复之前状态
            table[i][j] = '.';
            ca[j] = cb[i + j] = cc[n - 1 + (i - j)] = false;
        }
    }

    public static void main(String[] args) {
        System.out.println(solveNQueens(8));
    }
}

